Summary: Rademacher complexity is a powerful tool for producing generalization guarantees. The Rademacher complexity of a class H on a sample S is roughly the expected maximum gap between training and test performance if S were randomly partitioned into training and test sets, and we took the maximum over all h in H (eqn 11). This paper makes the observation that the core steps in the standard generalization bound proof will still go through if instead of taking the max over all h in H, you only look at the h's that your procedure can possibly output when given half of a double sample (Lemma 1). While unfortunately the usual final (or initial) high-probability step in this argument does not seem to go through directly, the paper shows (Theorem 2) that one can nonetheless get a useful generation bound from this using other means. The paper then shows how this generalization bound yields good sample complexity guarantees for a number of natural auction classes.